package com.cdream.basic.algorithm.leetcode.linkedlist;

import java.util.HashMap;

public class Question146 {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        System.out.println(lruCache.get(2));
        lruCache.put(2,6);
        System.out.println(lruCache.get(1));
        lruCache.put(1,5);
        lruCache.put(1,2);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(2));


    }
}
class LRUCache {
    public HashMap<Integer,Node> map = new HashMap<>();
    Node head;
    Node tail;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.next = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if(n==null){
            return -1;
        }
        n.remove();
        head.addNext(n);
        return n.value;
    }

    public void put(int key, int value) {

        Node n = map.get(key);
        if(n !=null){
            n.value = value;
        }else {
            if(map.size()==capacity){
                Node p = tail.prev;
                map.remove(p.key);
                p.remove();
            }
            Node newNode = new Node(key,value);
            map.put(key,newNode);
            head.addNext(newNode);
        }
    }


}
class Node{
    Node prev;
    Node next;
    int value;
    int key;
    public Node(){

    }
    public Node(int key,int value){
        this.key = key;
        this.value = value;
    }
    void addNext(Node n){
        Node next = this.next;

        this.next = n;
        n.prev = this;

        n.next = next;
        next.prev = n;

    }
    void remove(){
        prev.next = next;
        next.prev = prev;
    }

}
